package cn.zifangsky.array.questions;

import cn.zifangsky.linkedlist.LinkedList;
import org.junit.Test;

/**
 * 生成窗口最大值数组
 *
 * @author zifangsky
 * @date 2019/12/20
 * @since 1.0.0
 */
public class Problem_003_SlidingWindowMaxArray {


    @Test
    public void testMethods(){
        //定义测试数据
        int[] arr = {4, 3, 5, 4, 3, 3, 6, 7};
        //定义测试窗口大小
        int w = 3;

        System.out.println("窗口最大值数组是：" + this.toString(this.getMaxWindow(arr, w)));
    }


    /**
     * 获取最大窗口
     * @author zifangsky
     * @date 2019/12/20 16:34
     * @since 1.0.0
     * @param arr 数组
     * @param w 窗口大小
     * @return int[]
     */
    private int[] getMaxWindow(int[] arr, int w){
        if(arr == null || w < 1 || arr.length < w){
            return null;
        }

        //1. 定义一个双端队列和结果数组
        LinkedList<Integer> list = new LinkedList<>();
        int[] maxWindowArr = new int[arr.length - w + 1];
        int index = 0;

        for(int i = 0; i < arr.length; i++){
            //2. 如果队列的对尾元素小于等于arr[i]，则一直做出队操作
            while (!list.isEmpty() && arr[list.peekLast()] <= arr[i]){
                list.pollLast();
            }

            //3. 新的较大元素的下标从对尾入队
            list.offerLast(i);

            //4. 判断队首元素是否已经过期，如果过期则做出队操作
            if(list.peekFirst() == (i - w)){
                list.pollFirst();
            }

            //5. 将当前窗口的最大元素放入到结果数组中
            if(i >= (w - 1)){
                maxWindowArr[index++] = arr[list.peekFirst()];
            }
        }

        return maxWindowArr;
    }

    /**
     * 格式化输出数组
     */
    private String toString(int[] a) {
        if (a == null) {
            return "null";
        }
        int indexMax = a.length - 1;
        if (indexMax == -1) {
            return "[]";
        }

        StringBuilder b = new StringBuilder();
        b.append('[');
        for (int i = 0; ; i++) {
            b.append(a[i]);
            if (i == indexMax) {
                return b.append(']').toString();
            }
            b.append(", ");
        }
    }

}
